#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>

#define MIN(a, b) (((a) <= (b)) ? (a) : (b))
#define NUM 16384000
//#define DEBUG

void merge(long* array, long* tmp, int s, int m, int e) {
    int i, j, k;
    for (i = s; i < e; ++i)
        tmp[i] = array[i];

    i = s;
    j = m;
    k = s;
    
    while (i < m && j < e) {
        if (tmp[i] <= tmp[j])
            array[k++] = tmp[i++];
        else
            array[k++] = tmp[j++];
    }

    while (i < m)
        array[k++] = tmp[i++];
    while (j < e)
        array[k++] = tmp[j++];
}

void merge_sort(long* array, long* tmp, int len) {
    int step, i;

    for (step = 2; step < len * 2; step *= 2) {
        for (i = 0; i <= len - step; i += step) {
            merge(array, tmp, i, i + step / 2, i + step);
        }
        if (len - i > step / 2)
            merge(array, tmp, i, i + step / 2, len);
    }
}

int main() {
    long* array = (long *)malloc(NUM * sizeof(long));
    long* tmp = (long *)malloc(NUM * sizeof(long));
    int i;
    clock_t start, end;
    double duration;

    srand(time(0));
    for (i = 0; i < NUM; ++i)
        array[i] = rand() % (10 * NUM);

#ifdef DEBUG
    for (i = 0; i < NUM; ++i)
        printf("%ld ", array[i]);
    printf("\n");
#endif

    start = clock();
    merge_sort(array, tmp, NUM);
    end = clock();

#ifdef DEBUG
    for (i = 0; i < NUM; ++i)
        printf("%ld ", array[i]);
    printf("\n");
#endif

    duration = (double)(end - start);
    printf("%.8f\n", (duration / CLOCKS_PER_SEC));

    return 0;
}


